package solution1.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Solution15 {

    //1.移除元素
    public int removeElement(int[] nums, int val) {
        int fast = 0;
        int slow = 0;
        while(fast < nums.length) {
            if(nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    //2.三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            if(nums[i] > 0) { //第一个元素都大于零了，后面肯定大于零
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum < 0) {
                    while(left < right && nums[left] == nums[++left]){}
                } else if(sum > 0) {
                    while(left < right && nums[right] == nums[--right]){}
                } else {
                    //找到了
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while(left < right && nums[left] == nums[++left]){}
                    while(left < right && nums[right] == nums[--right]){}
                }
            }
        }
        return res;
    }

    //3.翻转链表
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //归并排序
    public void mergeSort(int[] arr) {
        mergeFun(arr, 0, arr.length - 1);
    }

    private void mergeFun(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeFun(arr, left, mid);
        mergeFun(arr, mid + 1, right);
        merge(arr, left, right, mid);
    }

    private void merge(int[] arr, int left, int right, int mid) {
        int[] tmpArr = new int[right - left + 1];
        int index = 0;
        int s1 = left;
        int s2 = mid + 1;
        while(s1 <= mid && s2 <= right) {
            if(arr[s1] < arr[s2]) {
                tmpArr[index++] = arr[s1++];
            } else {
                tmpArr[index++] = arr[s2++];
            }
        }
        while(s1 <= mid) {
            tmpArr[index++] = arr[s1++];
        }
        while(s2 <= right) {
            tmpArr[index++] = arr[s2++];
        }
        for(int i = 0; i < index; i++) {
            arr[i + left] = tmpArr[i];
        }
    }

    //希尔排序
    public void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap > 1) {
            gap >>= 1;
            shellInsertSort(arr, gap);
        }
        shellInsertSort(arr, 1);
    }

    private void shellInsertSort(int[] arr, int gap) {
        for(int i = gap; i < arr.length; i++) {
            int key = arr[i];
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(arr[j] > key) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = key;
        }
    }

}

class Main1 {
    public static void main(String[] args) {
        int[] arr = {3,1,4,6,5,7,8,0};
        Solution15 solution15 = new Solution15();
        solution15.shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}